public class Test29 {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] len = new int[n];
        int[] count = new int[n];
        int max = 1;
        int ret = 1;
        for(int i = 0;i < n;i++) len[i] = count[i] = 1;
        for(int i = 1;i < n;i++) {
            for(int j = i - 1;j >= 0;j--) {
                if(nums[i] > nums[j]) {
                    if(len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        count[i] = count[j];
                    }else if(len[j] + 1 == len[i]) {
                        count[i] += count[j];
                    }
                }
            }
            if(len[i] > max) {
                max = len[i];
                ret = count[i];
            }else if(len[i] == max) {
                ret += count[i];
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        Test29 test29 = new Test29();
        int[] arr = {84,-48,-33,-34,-52,72,75,-12,72,-45};
        System.out.println(test29.findNumberOfLIS(arr));
    }
}
